/*
 * Author: Wang Hsutung
 * Date: 2015/11/05
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef std::vector<std::string> strlist;

strlist popSequences(string str)
{
    strlist ret;
    const size_t len = str.size();

    if (len == 0) {
        ret.push_back(str);
        return ret;
    }

    for (size_t i = 0; i < len; ++i) {
        string left = str.substr(0, i);
        strlist ahead  = popSequences(left);

        string right = str.substr(i, len - i - 1);
        strlist behind = popSequences(right);

        for(size_t i = 0; i < ahead.size(); ++i)
            for(size_t j = 0; j < behind.size(); ++j)
                ret.push_back(ahead[i] + str[len - 1] + behind[j]);
    }
    return ret;
}


int main(int argc, char *argv[])
{
    strlist ans = popSequences("1234");

    for(size_t i = 0; i < ans.size(); ++i)
        cout << "(" << i + 1 << "):\t" << ans[i] << endl;

    return 0;
}

